---

Parallel N-Dimensional Exact Signed Euclidean Distance Transform

 

Robert Staubs, Andriy Fedorov, Leonidas Linardakis, Benjamin Dunton and Nikos Chrisochoides.

 

Published in Insight Journal, 2006

 

Abstract

 

The computation speed for distance transforms becomes important in a wide variety of image processing applications. Current ITK library filters do not see any benefit from a multithreading environment. We introduce a three-dimensional signed parallel implementation of the exact Euclidean distance transform algorithm developed by Maurer et al. with a theoretical complexity of O(n/p) for n voxels and p threads. Through this parallelization and efficient use of data structures we obtain approximately 3 times mean speedup on standard tests on a 4-processor machine compared with the current ITK exact Euclidean distance transform filter.